

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class LRUcache extends LinkedHashMap<Integer, Integer> {
    public int capacity;

    public LRUcache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }


    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

}



class LRUCache {
    static class LinkedNode {
        private int key;
        private int val;
        private LinkedNode pre;
        private LinkedNode back;

        LinkedNode(){}
        LinkedNode(int _key, int _val, LinkedNode pre, LinkedNode back) {
            this.key = _key;
            this.val = _val;
            this.pre = pre;
            this.back = back;
        }
    }

    private int capacity;
    private Map<Integer, LinkedNode> map;
    private LinkedNode head;
    private LinkedNode tail;
    private int count;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        head = new LinkedNode();
        tail = new LinkedNode();
        head.back = tail;
        tail.pre = head;



    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        else {
            LinkedNode node = map.get(key);
            node.pre.back = node.back;
            node.back.pre = node.pre;

            node.pre = head;
            node.back = head.back;
            head.back = node;
            node.back.pre = node;

            return node.val;

        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            LinkedNode node = map.get(key);
            node.val = value;

            node.pre.back = node.back;
            node.back.pre = node.pre;

            node.pre = head;
            node.back = head.back;
            head.back = node;
            node.back.pre = node;
        } else {
            if (count >= capacity) {
                map.remove(tail.pre.key);
                tail.pre.pre.back = tail;
                tail.pre = tail.pre.pre;
                count--;
            }
            LinkedNode node = new LinkedNode(key, value, head, head.back);
            map.put(key, node);
            node.back.pre = node;
            head.back = node;
            count ++;
        }
    }
}

class LRUCache1 {
    class DLinkedList {
        private int key;
        private int val;
        private DLinkedList prev;
        private DLinkedList next;
        DLinkedList() {}
        DLinkedList(int _key, int _value, DLinkedList _prev, DLinkedList _next) {
            this.key = _key;
            this.val = _value;
            this.prev = _prev;
            this.next = _next;
        }
    }

    private int capacity;
    private Map<Integer, DLinkedList> map = new HashMap<>();
    private int size = 0;
    DLinkedList head;
    DLinkedList tail;

    public LRUCache1(int capacity) {
        this.capacity = capacity;
        head = new DLinkedList();
        tail = new DLinkedList();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        moveToHead(map.get(key));
        return map.get(key).val;

    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).val = value;
            moveToHead(map.get(key));
        } else {
            if (size >= capacity) {
                removeLast();

            }
            DLinkedList node = new DLinkedList(key, value, null, null);
            insertHead(node);

        }
    }
    public void moveToHead(DLinkedList node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;

        node.prev = head;
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
    }
    public void removeLast() {
        map.remove(tail.prev.key);
        tail.prev.prev.next = tail;
        tail.prev = tail.prev.prev;
        size--;
    }
    public void insertHead(DLinkedList node) {
        node.prev = head;
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
        map.put(node.key, node);
        size++;
    }



    // 就是一个可以包含双向链表的map
}

